#include<iostream>
#include<vector>
using namespace std;
/*
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。
请你从 nums 中找出并返回总和为 target 的元素组合的个数
解题思路：
改题目给的仍然是完全背包类问题，但是与零钱兑换的问题不一样，改题目相同元素的不同排列是算作不同种，所以是一个排列的题目
dp[j]表示的是装满容量为j的背包最多有dp[j]种方法
且dp[j]+=dp[j-nums[i]]
*/
int dp(vector<int> nums,int target)
{
    //初始化dp数组
    vector<int> dp(target+1);
    dp[0] = 1;
    //遍历搭dp数组时应该先遍历背包然后再遍历物品
    for(int i=1;i<=target;i++)
    {
        for(int j=0;j<nums.size();j++)
        {
            if(nums[j]<=i&&dp[i - nums[j]] < INT_MAX - dp[i])
            {
                dp[i]+=dp[i-nums[j]];
                cout<<dp[i]<<" ";
            }
        }
        cout<<endl;
    }
    return dp[target];
}
int main()
{
    cout<<"enter target:"<<endl;
    int target;
    cin>>target;
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
    {
        cin>>nums[i];
    }
    cout<<dp(nums,target);
    return 0;
}